package leetCode.offer42;

import java.util.*;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * 要求时间复杂度为O(n)。
 * 示例1:
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释:连续子数组[4,-1,2,1] 的和最大，为6。
 *
 */
public class Solution2 implements Solution{


    /**
     * 此方法也超出时间限制
     * @param nums
     * @return
     */
    @Override
    public int maxSubArray(int[] nums) {
        if(nums.length==1) return nums[0];
        if(nums.length==2){
            int sun = nums[0]+nums[1];
            if(sun>nums[0]&&sun>nums[1]){
                return sun;
            }
            return Math.max(nums[0], nums[1]);
        }
        // 存储顺序子数组和
        int[] sum = new int[nums.length+1];
        sum[0] = 0;
        int num = 0;
        for(int i=0;i<nums.length;i++){
            num+=nums[i];
            sum[i+1] = num;
        }
        return maxProfit(sum);
    }

    /**
     * 求出prices[i] - prices[j] 的最大值
     * 其中i>j
     * @param prices 目标数组
     * @return
     */
    public int maxProfit(int[] prices) {
        Map<Integer,Integer> map1 = new HashMap<>();
        Map<Integer,Integer> map2 = new HashMap<>();
        List<Integer> help = new ArrayList<>();
        for(int i=0;i<prices.length;i++) {
            if(!map1.containsKey(prices[i])){
                map1.put(prices[i],i);
                help.add(prices[i]);
            }
            map2.put(prices[i],i);
        }
        Collections.sort(help);
        int result = -Integer.MAX_VALUE;
        for(int j = help.size()-1;j>=0;j--) {
            for(int i=0;i<help.size();i++) {
                if(map2.get(help.get(j))>map1.get(help.get(i))) {
                    if(help.get(j)-help.get(i)>result){
                        result = help.get(j)-help.get(i);
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] param = {-2,-3,-1};
        System.out.println(new Solution2().maxSubArray(param));
    }


}
